import java.util.HashMap;
import java.util.Map;

/**
 * Huffman Encoding.
 */
public class Huffman
{
    public static void main(String[] args)
    {
        //System.out.println(Huffman.encode("chris"));
        System.out.println(Huffman.decodeString(Huffman.encode("chris"),Huffman.buildHuffmanTree(Huffman.buildFrequencyTable("chris"))));
    }

    public static String encode(String str)
    {
       return Huffman.encodeString(str, Huffman.buildEncoder(Huffman.buildFrequencyTable(str)));
    }

	/**
	 * Builds the frequency table for each character in the given string.
	 * Map<Character, Integer> should be a mapping of characters to their
	 * respective frequencies.
	 *
	 * @param str The String to be encoded.
	 */
	public static Map<Character, Integer> buildFrequencyTable(String str)
    {
        HashMap<Character, Integer> myMap = new HashMap<Character, Integer>();
        for(int i = 0; i < str.length(); i++)
        {
            char c = str.charAt(i);
            if(!myMap.containsKey(c))
            {
                myMap.put(c, 1);
            }
            else
            {
                int freq = myMap.get(c);
                myMap.put(c,freq+1);
            }
        }
        if(str.length() == 0)
        {
            myMap.put('\0',1);
        }
		return myMap;
	}

	/**
	 * Builds the encoder map that pairs a Character with it's corresponding 
	 * Huffman encoding. Map<Character, String> should be a map of characters
	 * to their Huffman encoding.
	 *
	 * @param frequencyTable The frequency table of characters
	 */
	public static Map<Character, String> buildEncoder(Map<Character, Integer> frequencyTable)
    {
        Map<Character, String> myMap;
		HuffmanTree myTree = Huffman.buildHuffmanTree(frequencyTable);
        if(myTree.head.left == null)
        {
            myMap = new HashMap<Character, String>();
            myMap.put(myTree.head.character,"0");
        }
        else
        {
            myMap = myTree.treeTraversal(myTree.head, "", new HashMap<Character, String>());
        }
		return myMap;
	}

	/**
	 * Builds a huffman tree that can be used for decoding from the frequency table
	 * 
	 * @param frequencyTable The frequency table of characters
	 */
	public static HuffmanTree buildHuffmanTree(Map<Character, Integer> frequencyTable)
    {
		return new HuffmanTree(frequencyTable);
	}
	
	/**
	 * Encodes a String
	 *
	 * @param  input The String to be encoded.
	 * @param  encoder an encoder that can be used to encode the input
	 * @return String The resulting encoded String.
	 */
	public static String encodeString(String input, Map<Character, String> encoder)
    {
        String encoded = "";
        for(int i = 0; i < input.length(); i++)
        {
            Character c = input.charAt(i);
            encoded += encoder.get(c);
        }
		return encoded;
	}
		
	/**
	 * Decodes a String
	 *
	 * @param  input The String to be decoded.
	 * @param  tree A huffman tree generated from the input
	 * @return String The decoded String.
	 */
	public static String decodeString(String input, HuffmanTree tree)
    {
        return tree.decode(input);
	}

}